program Lists

type ListNodePtr = ->ListNode
     ListNode = compound
       next: ListNodePtr
       data: int
     end
     ListPtr = ListNodePtr
     
var  list : ListPtr

EmptyList(): ListPtr
begin
  return null
end EmptyList

NewListNode(in data:int):ListNodePtr
  var n: ListNodePtr
begin
  n := New(in ListNode)
  if n=null then
    Write(in "error: heap overflow")
    halt
  end
  n->next := null
  n->data := data
  return n
end NewListNode

Prepend(io list: ListPtr  in n: ListNodePtr)
begin
  n->next := list   -- 1. append old list to new node
  list := n         -- 2. new list = ( n, old list )
end Prepend

Append(io list: ListPtr  in n: ListNodePtr)
  var last: ListNodePtr
begin
  if list = null then  -- list is empty
    list := n
  else  -- list != null, list is not empty
    -- search last node
    last := list
    while last->next != null do
      last := last->next
    end -- while
    -- append n to last node
    last->next := n  -- new list = ( old list, n )
  end -- if
end Append

WriteList(in l: ListPtr)
  var n: ListNodePtr
begin
  n := l
  Write(in "write list:")
  while n!=null do
    Write(in "element<" in n->data in ">")
    n := n->next
  end
end WriteList

begin
  list := EmptyList()
  Prepend(io list in NewListNode(in 5)) 
  Prepend(io list in NewListNode(in 4))
  Append(io list in NewListNode(in 6))
  WriteList(in list)
  Read()
end
